This specification relates to error control for data that is subject to corruptions or erasures.
Various techniques are used for error control of data in the face of errors and erasures in the data. A number of techniques are applicable to data that is represented or representable as N channels. In some techniques, in addition to the N channels of data, redundant data in the form of parity is also computed to form additional channels, and the original and redundant channels are distributed each to a separate storage system. If one of the storage systems fails, and therefore represents an “erasure” of the data for the corresponding channel, a redundant parity channel can be used to reconstruct the data. This general approach is used in various variants of RAID (Redundant Array of Inexpensive Disks) systems.
Parity, as well as various other forms of error detecting and correcting codes (generally referred to as Error Correcting Codes, ECCs), have been applied to blocks of data in storage systems, such as in solid state memories and magnetic disk systems. In general, with the addition of M redundant channels, M coincident erasures or coincident corruptions can be corrected in N data channels. RAID- and ECC-type approaches have also been applied when the storage devices are geographically distributed.
Parity approaches have also been used for multiple channels of streaming data, such as parallel bit streams stored on and retrieved from a magnetic tape storage. For example, a stream of parity bits are computed and stored with the data on the tape, with each parity bit being computed from a “stripe” of data bits from the data streams, such as from a stripe across corresponding bits of all the channels. In some approaches, multiple streams of parity bits are computed using diagonal stripes through the data (i.e., using different time offsets for each channel when computing a parity value). With multiple parity streams, one or more errors can be detected, and corrected under certain conditions.